package problem30_Substring_with_Concatenation_of_All_Words;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
/*
 * Try to think this problem straightforward:
 * Say in L there are m strings with length n.
 * What string is required to match in S? A length of m*n string start with each position in S.
 * What is a match? In the m*n long string, every string in L appear only once.
 */
import java.util.Map;

public class MySolution {
	public List<Integer> findSubstring(String s, String[] words) {
		List<Integer> result=new LinkedList<>();
		Map<String,Integer> toBeFound=new HashMap<>();
		for(String word:words){
			if(toBeFound.containsKey(word)){
				toBeFound.put(word, toBeFound.get(word)+1);
			}else{
				toBeFound.put(word, 1);
			}
		}
		int i=0,m=words.length,n=words[0].length();
		while(i+m*n<=s.length()){
			Map<String,Integer> found=new HashMap<>(toBeFound);
			for(int j=0;j<m;j++){
				String word=s.substring(i+j*n,i+j*n+n);
				if(found.containsKey(word)){
					if(found.get(word)==1)
						found.remove(word);
					else
						found.put(word, found.get(word)-1);
				}else{
					break;
				}
			}
			if(found.size()==0) result.add(i);
			i++;
		}
		return result;
	}
	
	public static void main(String[] args){
		System.out.println(new MySolution().findSubstring("barfoothefoobarman", new String[]{"foo","bar"}));
	}
}
